{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #合并 K 个升序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #divide-and-conquer #heap-priority-queue #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #分治 #堆（优先队列） #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mergeKLists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并 K 个升序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个链表数组，每个链表都已经按升序排列。</p>\n",
    "\n",
    "<p>请将所有链表合并到一个升序链表中，返回合并后的链表。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lists = [[1,4,5],[1,3,4],[2,6]]\n",
    "<strong>输出：</strong>[1,1,2,3,4,4,5,6]\n",
    "<strong>解释：</strong>链表数组如下：\n",
    "[\n",
    "  1-&gt;4-&gt;5,\n",
    "  1-&gt;3-&gt;4,\n",
    "  2-&gt;6\n",
    "]\n",
    "将它们合并到一个有序链表中得到。\n",
    "1-&gt;1-&gt;2-&gt;3-&gt;4-&gt;4-&gt;5-&gt;6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lists = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lists = [[]]\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>k == lists.length</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10^4</code></li>\n",
    "\t<li><code>0 &lt;= lists[i].length &lt;= 500</code></li>\n",
    "\t<li><code>-10^4 &lt;= lists[i][j] &lt;= 10^4</code></li>\n",
    "\t<li><code>lists[i]</code> 按 <strong>升序</strong> 排列</li>\n",
    "\t<li><code>lists[i].length</code> 的总和不超过 <code>10^4</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 23&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/merge-k-sorted-lists/\">https://leetcode-cn.com/problems/merge-k-sorted-lists/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [vvXgSW](https://leetcode.cn/problems/vvXgSW/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [vvXgSW](https://leetcode.cn/problems/vvXgSW/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4,5],[1,3,4],[2,6]]', '[]', '[[]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "# # 最小堆\n",
    "# class Solution:\n",
    "#     def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "#         import heapq\n",
    "#         dummy = ListNode(-1)\n",
    "#         p = dummy\n",
    "#         heap = []\n",
    "#         for i in range(len(lists)):\n",
    "#             if lists[i]:\n",
    "#                 heapq.heappush(heap, (lists[i].val, i))\n",
    "#                 lists[i] = lists[i].next\n",
    "#         while heap:\n",
    "#             ival, idx = heapq.heappop(heap)\n",
    "#             p.next = ListNode(ival)\n",
    "#             p = p.next\n",
    "#             if lists[idx]:\n",
    "#                 heapq.heappush(heap, (lists[idx].val, idx))\n",
    "#                 lists[idx] = lists[idx].next\n",
    "#         return dummy.next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        if len(lists) < 2:\n",
    "            return lists[0]\n",
    "        while len(lists) >= 2:\n",
    "            lists.insert(0, self.mergeTwoLists(lists.pop(), lists.pop()))\n",
    "        return lists[0]\n",
    "    def mergeTwoLists(self, list1, list2):\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        while list1 and list2:\n",
    "            if list1.val < list2.val:\n",
    "                p.next = list1\n",
    "                list1 = list1.next\n",
    "            else:\n",
    "                p.next = list2\n",
    "                list2 = list2.next\n",
    "            p = p.next\n",
    "        p.next = list1 if list1 else list2\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        head = current = ListNode(0)\n",
    "        res = current\n",
    "        while res:\n",
    "            res = None\n",
    "            i = 0\n",
    "            for idx, node in enumerate(lists):\n",
    "                if node and(res is None or node.val < res.val):\n",
    "                    res = node\n",
    "                    i = idx\n",
    "            if res:\n",
    "                current.next = res\n",
    "                current = current.next\n",
    "                lists[i] = lists[i].next\n",
    "        return head.next\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        L = ListNode(-1)\n",
    "        while len(lists) > 1:\n",
    "            i, j = 0, len(lists) - 1\n",
    "            while i < j:\n",
    "                l1, l2, r = lists[i], lists[j], L\n",
    "                while l1 and l2:\n",
    "                    if l1.val < l2.val:\n",
    "                        r.next = l1\n",
    "                        l1 = l1.next\n",
    "                    else:\n",
    "                        r.next = l2\n",
    "                        l2 = l2.next\n",
    "                    r = r.next\n",
    "                r.next = l1 if l1 else l2\n",
    "                lists[i] = L.next\n",
    "                lists.pop()\n",
    "                i, j = i + 1, j - 1\n",
    "        return lists[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        x = None\n",
    "        for y in lists:\n",
    "            x = self.merge(x, y)\n",
    "        return x\n",
    "\n",
    "    \n",
    "    def merge(self, a: ListNode, b: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        x = dummy\n",
    "        while a and b:\n",
    "            if a.val < b.val:\n",
    "                x.next = a\n",
    "                a = a.next\n",
    "            else:\n",
    "                x.next = b\n",
    "                b = b.next\n",
    "            x = x.next\n",
    "        if a:\n",
    "            x.next = a\n",
    "        if b:\n",
    "            x.next = b\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "    # def __lt__(self, other):\n",
    "    #     return self.val < other.val \n",
    "\n",
    "class Solution:\n",
    "    def __lt__(self, other):\n",
    "        return self.val < other.val\n",
    "    ListNode.__lt__ = __lt__\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        heap = []\n",
    "        for l in lists:\n",
    "            if l:\n",
    "                heapq.heappush(heap, l)\n",
    "        \n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        while heap:\n",
    "            node = heapq.heappop(heap)\n",
    "            cur.next = node\n",
    "            cur = cur.next\n",
    "            if node.next:\n",
    "                heapq.heappush(heap, node.next)\n",
    "        \n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def mergetTwolist(l1, l2):\n",
    "            res = ListNode(-1)\n",
    "\n",
    "            cur = res\n",
    "            while l1 and l2:\n",
    "\n",
    "                if l1.val <= l2.val:\n",
    "\n",
    "                    cur.next = l1\n",
    "                    l1 = l1.next\n",
    "                else:\n",
    "                    cur.next = l2\n",
    "                    l2 = l2.next\n",
    "                cur = cur.next\n",
    "\n",
    "            if l2:\n",
    "                l1 = l2\n",
    "            cur.next = l1\n",
    "            return res.next\n",
    "\n",
    "        n = len(lists)\n",
    "\n",
    "        if n == 0: return None\n",
    "\n",
    "        if n == 1: return lists[0]\n",
    "        if n == 2: return mergetTwolist(lists[0], lists[1])\n",
    "\n",
    "        return mergetTwolist(self.mergeKLists(lists[:n // 2]), self.mergeKLists(lists[n//2:]))            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        def __lt__(a: ListNode, b: ListNode) -> bool:\n",
    "            return a.val < b.val\n",
    "        ListNode.__lt__ = __lt__\n",
    "\n",
    "        if not lists:\n",
    "            return None\n",
    "        \n",
    "        minheap = []\n",
    "        for l in lists:\n",
    "            if l:\n",
    "                heapq.heappush(minheap, (l.val, l))\n",
    "        \n",
    "        dummyNode = ListNode(-1)\n",
    "        tail = dummyNode\n",
    "        while minheap:\n",
    "            _, currentMin = heapq.heappop(minheap)\n",
    "            tail.next = currentMin\n",
    "            if currentMin.next:\n",
    "                heapq.heappush(minheap, (currentMin.next.val, currentMin.next))\n",
    "            tail = tail.next \n",
    "        return dummyNode.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "ListNode.__lt__= lambda self, other: self.val < other.val\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "\n",
    "        if not lists:\n",
    "            return None\n",
    "\n",
    "        pq = []\n",
    "        for head in lists:\n",
    "            if head:\n",
    "                heapq.heappush(pq, (head.val, head))\n",
    "        \n",
    "        while pq:\n",
    "            node = heapq.heappop(pq)[1]\n",
    "            p.next = node\n",
    "            if node.next:\n",
    "                heapq.heappush(pq, (node.next.val, node.next))\n",
    "            p = p.next\n",
    "        \n",
    "        return dummy.next\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        class Node(ListNode):\n",
    "            def __lt__(self,other):\n",
    "                return self.val < other.val\n",
    "        queue = [\n",
    "            Node(node.val, node.next)\n",
    "            for node in lists if node\n",
    "        ]\n",
    "        heapify(queue)\n",
    "        dump= ListNode(-1)\n",
    "        cur = dump\n",
    "        while(queue):\n",
    "            tmp =heappop(queue)\n",
    "            cur.next = ListNode(tmp.val)\n",
    "            cur=cur.next\n",
    "            if tmp.next:\n",
    "                tmp = tmp.next\n",
    "                heappush(queue,Node(tmp.val,tmp.next))\n",
    "            \n",
    "        return dump.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class MyListNode:\n",
    "    def __init__(self, node):\n",
    "        self.node = node\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        return self.node.val < other.node.val\n",
    "    \n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        q = []\n",
    "        for node in lists:\n",
    "            if node:\n",
    "                heappush(q, MyListNode(node))\n",
    "        \n",
    "        head = ListNode(0)\n",
    "        cur = head\n",
    "        while q:\n",
    "            node = heappop(q).node\n",
    "            cur.next = node\n",
    "            cur = cur.next\n",
    "            if node.next:\n",
    "                heappush(q, MyListNode(node.next))\n",
    "        \n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        \n",
    "        #创建新链表的节点\n",
    "        h = ListNode()\n",
    "\n",
    "        #备份新链表的节点\n",
    "        newh = h\n",
    "\n",
    "        #把链表元素放入堆中,取最小元素\n",
    "        #heapq默认是小顶堆\n",
    "\n",
    "        #创建堆\n",
    "        s = []\n",
    "        for i in lists:\n",
    "            while i:\n",
    "                heapq.heappush(s,i.val)\n",
    "                i = i.next\n",
    "\n",
    "        while s:\n",
    "            t = heapq.heappop(s)\n",
    "            h.next =ListNode(t)\n",
    "            h = h.next\n",
    "        \n",
    "        return newh.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        minHeap = []\n",
    "        for x in lists:\n",
    "            while x:\n",
    "                heapq.heappush(minHeap, x.val)\n",
    "                x = x.next\n",
    "            \n",
    "        dummy = ListNode(-1)\n",
    "        x = dummy\n",
    "        while minHeap:\n",
    "            x.next = ListNode(heapq.heappop(minHeap))\n",
    "            x = x.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # https://labuladong.github.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc/#%E5%90%88%E5%B9%B6-k-%E4%B8%AA%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8\n",
    "# # 这道题我已经理解到了，二叉堆好厉害\n",
    "# # Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "#     def __lt__(self, other):\n",
    "#         return self.val < other.val\n",
    "\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "# class Solution:\n",
    "    \n",
    "#     def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "#         # ListNode.lt= lambda self, other: self.val < other.val\n",
    "#         if not lists:\n",
    "#             return None\n",
    "        \n",
    "#         # 既然是合并链表，一般都是要构建一个新链表，然后一个个接到新链表上\n",
    "#         dummy = ListNode(0)\n",
    "#         p = dummy\n",
    "        \n",
    "#         pq = []\n",
    "#         for head in lists:\n",
    "#             if head:\n",
    "#                 # 初始化，构建最小堆\n",
    "#                 # 优先级队列中的每个元素是一个元组，第一个元素是链表结点的值，第二个元素是链表结点的引用\n",
    "#                 heapq.heappush(pq, (head.val, head))\n",
    "\n",
    "#         # 最小堆构建完成后，就开始拿取最小堆里的元素，接到新的链表上去\n",
    "#         while pq:\n",
    "#             # 先从最小堆里，去除堆顶节点(也就是第一个节点，这里不是数组，没有idx为0的，第一个节点就是1)\n",
    "#             node = heap.heappop(pq[1]) # 这里的1是指（head.val, head）中的head，因为idx为1，所以写1\n",
    "#             p.next = node # 这里不需要把node的下一个节点断开，因为后面始终都会覆盖掉\n",
    "\n",
    "#             if node.next:\n",
    "#                 heap.heappush(pq, (node.next.val, node.next))\n",
    "\n",
    "#             # p节点前进一个\n",
    "#             p = p.next\n",
    "        \n",
    "#         return dummy.next\n",
    "\n",
    "\n",
    "# 创建一些链表的对象\n",
    "# l1 = ListNode(1, ListNode(4, ListNode(5)))\n",
    "# l2 = ListNode(1, ListNode(3, ListNode(4)))\n",
    "# l3 = ListNode(2, ListNode(6))\n",
    "\n",
    "# # 把它们放到一个列表中\n",
    "# lists = [l1, l2, l3]\n",
    "\n",
    "# # 创建一个优先级队列\n",
    "# pq = []\n",
    "# for head in lists:\n",
    "#     if head:\n",
    "#         heapq.heappush(pq, (head.val, head))\n",
    "\n",
    "# # 打印优先级队列的内容\n",
    "# print(\"The priority queue is: \")\n",
    "# for item in pq:\n",
    "#     print(item)\n",
    "\n",
    "# # 运行这段代码，可以得到以下的输出：\n",
    "# # The priority queue is: \n",
    "# # (1, 1 -> 4 -> 5)\n",
    "# # (1, 1 -> 3 -> 4)\n",
    "# # (2, 2 -> 6)\n",
    "# # 优先级队列中的每个元素是一个元组，第一个元素是链表结点的值，第二个元素是链表结点的引用。\n",
    "# # 优先级队列会按照元组的第一个元素的大小来排序，也就是说，最小的值会在队列的最前面\n",
    "\n",
    "\n",
    "# 方法：优先级队列，构建最小堆\n",
    "# heapq是python的一个堆操作模块，主要用于实现堆的数据结构\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        # 既然是合并链表，一般都是要构建一个新链表，然后一个个接到新链表上\n",
    "        dummy = ListNode(0)\n",
    "        p = dummy\n",
    "\n",
    "        pq = [] # 优先级队列\n",
    "        for idx, head in enumerate(lists):\n",
    "            # 初始化，构建最小堆\n",
    "            # 优先级队列中的每个元素是一个元组，第一个元素是链表结点的值，第二个元素是链表的索引\n",
    "            while head:\n",
    "                # 最后那个i，就是跟上面代码的不同之处，因为listnode之间无法比较大小，所以这里要写i，\n",
    "                # 相当于比较大小了，因为每个idx对应一个节点嘛\n",
    "                heapq.heappush(pq, (head.val, idx))\n",
    "                head = head.next\n",
    "        \n",
    "        # 以上就是最小堆构建完成了\n",
    "        # 接下来要一个个接到新链表上\n",
    "        # 最小堆构建完成后，就开始拿取最小堆里的元素，接到新的链表上去\n",
    "        while pq:\n",
    "            # 先从最小堆里，去除堆顶节点(也就是第一个节点，这里不是数组，没有idx为0的，第一个节点就是1)，这是针对上面方法说的\n",
    "            value, idx = heappop(pq)\n",
    "            node = ListNode(value)\n",
    "            p.next = node\n",
    "            while node.next:\n",
    "                heappush(pq, (node.next.val, idx))\n",
    "                node = node.next\n",
    "\n",
    "            p = p.next\n",
    "        \n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "\n",
    "# 讲解二叉堆：        \n",
    "# 创建一些链表的对象\n",
    "# l1 = ListNode(1, ListNode(4, ListNode(5)))\n",
    "# l2 = ListNode(1, ListNode(3, ListNode(4)))\n",
    "# l3 = ListNode(2, ListNode(6))\n",
    "\n",
    "# # 把它们放到一个列表中\n",
    "# lists = [l1, l2, l3]\n",
    "\n",
    "# # 创建一个优先队列\n",
    "# head = []\n",
    "# for i in range(len(lists)):\n",
    "#     while lists[i]:\n",
    "#         heapq.heappush(head, (lists[i].val, i))\n",
    "#         lists[i] = lists[i].next\n",
    "\n",
    "# # 打印优先队列的内容\n",
    "# print(\"The priority queue is: \")\n",
    "# for item in head:\n",
    "#     print(item)\n",
    "\n",
    "# 运行这段代码，可以得到以下的输出：\n",
    "# The priority queue is: \n",
    "# (1, 0)\n",
    "# (1, 1)\n",
    "# (2, 2)\n",
    "# (3, 1)\n",
    "# (4, 0)\n",
    "# (4, 1)\n",
    "# (5, 0)\n",
    "# (6, 2)\n",
    "# # 优先队列中的每个元素是一个元组，第一个元素是链表结点的值，第二个元素是链表的索引。\n",
    "# # 优先队列会按照元组的第一个元素的大小来排序，如果相同，就按照第二个元素的大小来排序，\n",
    "# # 也就是说，最小的值和最小的索引会在队列的最前面"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if len(lists) == 0 or len(lists) == 1 and lists[0] is None:\n",
    "            return None\n",
    "        if len(lists) == 1:\n",
    "            return lists[0]\n",
    "        pilots = []\n",
    "        ls_all = []\n",
    "        n = len(lists)\n",
    "        for i in range(n):\n",
    "            pilots.append(len(ls_all))\n",
    "            cur = lists[i]\n",
    "            while cur is not None:\n",
    "                ls_all.append(cur.val)\n",
    "                cur = cur.next\n",
    "        head = ListNode()\n",
    "        cur = head\n",
    "        # print(ls_all)\n",
    "        ls_all.sort()\n",
    "        for vl in ls_all:\n",
    "            new_node = ListNode(val = vl, next = None)\n",
    "            cur.next = new_node\n",
    "            cur = cur.next\n",
    "        return head.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        dummy_node = ListNode(-1)\n",
    "        p = dummy_node\n",
    "        new_lists = []\n",
    "        for x in lists:\n",
    "            if x is not None:\n",
    "                new_lists.append(x)\n",
    "        lists = new_lists\n",
    "\n",
    "        if len(lists) == 0:\n",
    "            return None\n",
    "        import heapq\n",
    "        heaps = [(x.val, i) for i, x in enumerate(lists)]\n",
    "        heapq.heapify(heaps)\n",
    "        total_nums = len(lists)\n",
    "        while(1):\n",
    "            top_v, index = heapq.heappop(heaps)\n",
    "            p.next = ListNode(top_v)\n",
    "            p = p.next\n",
    "            lists[index] = lists[index].next\n",
    "            if lists[index] is None:\n",
    "                total_nums -=1\n",
    "                if total_nums == 0:\n",
    "                    break\n",
    "            else:\n",
    "                heapq.heappush(heaps, (lists[index].val, index))\n",
    "        return dummy_node.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from bisect import insort_left\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        st = deque()\n",
    "\n",
    "        for i, l in enumerate(lists):\n",
    "            if not l:\n",
    "                continue\n",
    "            insort_left(st, (l.val, i))\n",
    "        print(st)\n",
    "        dummyHead = ListNode(-1)\n",
    "        pt = dummyHead\n",
    "\n",
    "        while st:\n",
    "            _, i = st.popleft()\n",
    "            l = lists[i]\n",
    "            pt.next = ListNode(l.val)\n",
    "            pt = pt.next\n",
    "            if l.next:\n",
    "                lists[i] = l.next\n",
    "                insort_left(st, (l.next.val, i))\n",
    "        \n",
    "        return dummyHead.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Meta:\n",
    "    def __init__(self, node = None):\n",
    "        self.node = node\n",
    "    \n",
    "    def __gt__(self, obj):\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        dummy_head = ListNode()\n",
    "        tail = dummy_head\n",
    "\n",
    "        heap = PriorityQueue()\n",
    "        for head in lists:\n",
    "            if head == None:\n",
    "                continue\n",
    "\n",
    "            heap.put((head.val, Meta(head)))\n",
    "            \n",
    "        while heap.qsize() != 0:\n",
    "            value, meta = heap.get()\n",
    "            node = meta.node\n",
    "\n",
    "            tail.next = node\n",
    "            tail = node\n",
    "\n",
    "            node = node.next\n",
    "            if node:\n",
    "                heap.put((node.val, Meta(node)))\n",
    "\n",
    "        tail.next = None\n",
    "        return dummy_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        print(1,lists)\n",
    "        lists = list(filter(lambda x: x != None, lists))\n",
    "        print(2,lists)\n",
    "        # for list in lists:\n",
    "        #     if list == None:\n",
    "        #         lists.remove(list)\n",
    "        # print(2,lists)\n",
    "        if len(lists) <= 0:\n",
    "            return None \n",
    "        head = ListNode(0)\n",
    "        tempHead = head\n",
    "        \n",
    "        while len(lists) > 1:\n",
    "            minNode = None\n",
    "            createIndex = 0\n",
    "            for index, nodeList in enumerate(lists):\n",
    "                if minNode == None:\n",
    "                    # print(\"a\", nodeList.val)\n",
    "                    minNode = nodeList\n",
    "                    createIndex = index\n",
    "                else:\n",
    "                    if minNode.val > nodeList.val:\n",
    "                        # print(\"b\", nodeList.val)\n",
    "                        minNode = nodeList\n",
    "                        createIndex = index\n",
    "            # print(\"c\", minNode.val)\n",
    "            head.next = minNode\n",
    "            head = minNode\n",
    "            if minNode.next == None:\n",
    "                lists.remove(minNode)\n",
    "            else:\n",
    "                # print(\"d\", minNode)\n",
    "                lists[createIndex] = lists[createIndex].next\n",
    "        #         print(\"e\", minNode)\n",
    "        #         print(\"f\",lists)\n",
    "                \n",
    "        # print(\"g\",lists)\n",
    "        if len(lists) >= 1:\n",
    "            head.next = lists[0]\n",
    "\n",
    "        return tempHead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        ans = []\n",
    "        tot = 0\n",
    "        for x in lists:\n",
    "            arr = []\n",
    "            while x != None:\n",
    "                arr.append(x.val)\n",
    "                x=x.next\n",
    "                tot += 1\n",
    "            ans.append(arr)\n",
    "        q=[]\n",
    "        n = len(ans)\n",
    "        l = ans\n",
    "        a = []\n",
    "        for i in range(n):\n",
    "            if (len(l[i]) > 0):\n",
    "                heapq.heappush(q, (l[i][0], i, 0))\n",
    "        for i in range(tot):\n",
    "            tt = heapq.heappop(q)\n",
    "            a.append(tt[0])\n",
    "            if (tt[2] + 1 < len(l[tt[1]])):\n",
    "                heapq.heappush(q, (l[tt[1]][tt[2]+1], tt[1], tt[2] + 1))\n",
    "        if(len(a) == 0):\n",
    "            return None\n",
    "        t = head = ListNode(a[0])\n",
    "        for j in range(1,len(a)):\n",
    "            t.next = ListNode(a[j])\n",
    "            t = t.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "\n",
    "        if len(lists)==0:\n",
    "            return None\n",
    "        temp=[]\n",
    "        for listNode in lists:\n",
    "            if listNode:\n",
    "                temp.append(listNode)\n",
    "        lists=temp\n",
    "\n",
    "        print(lists)\n",
    "        print(len(lists))\n",
    "        \n",
    "        if len(lists)==0:\n",
    "            return None\n",
    "\n",
    "        head=ListNode(-1)\n",
    "        p=head\n",
    "\n",
    "        \n",
    "\n",
    "        while len(lists)>0:\n",
    "            temp_node=ListNode(float(\"inf\"))\n",
    "            for listNode in lists:\n",
    "                if listNode.val<temp_node.val:\n",
    "                    temp_node=listNode\n",
    "            \n",
    "            lists.remove(temp_node)\n",
    "            if temp_node.next and temp_node.val != float(\"inf\"):\n",
    "                lists.append(temp_node.next)\n",
    "            # print(lists)\n",
    "            new_node=ListNode(temp_node.val)\n",
    "            p.next=new_node\n",
    "            p=new_node            \n",
    "        \n",
    "        # print(head.next)\n",
    "\n",
    "        return head.next\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "\n",
    "\n",
    "    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head = prev = ListNode(-1)\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                prev.next = ListNode(l1.val)\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                prev.next = ListNode(l2.val)\n",
    "                l2 = l2.next\n",
    "            \n",
    "            prev = prev.next\n",
    "        \n",
    "        prev.next = l1 if l1 else l2\n",
    "    \n",
    "        return head.next\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        n = len(lists)\n",
    "        if n == 0:\n",
    "            return None\n",
    "\n",
    "        if n == 1:\n",
    "            return lists[0]\n",
    "\n",
    "        if n == 2:\n",
    "            return self.mergeTwoLists(lists[0], lists[1])\n",
    "\n",
    "        m = n // 2\n",
    "\n",
    "        return self.mergeTwoLists(self.mergeKLists(lists[0:m]), self.mergeKLists(lists[m:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def mergeTow(self, list1: ListNode, list2: ListNode) -> ListNode:\n",
    "        head = ListNode()\n",
    "        curr = head\n",
    "        while list1 and list2:\n",
    "            if list1.val < list2.val:\n",
    "                next_node = ListNode(list1.val)\n",
    "                list1 = list1.next\n",
    "            else:\n",
    "                next_node = ListNode(list2.val)\n",
    "                list2 = list2.next\n",
    "            curr.next = next_node\n",
    "            curr = curr.next\n",
    "        \n",
    "        while list1:\n",
    "            curr.next = ListNode(list1.val)\n",
    "            curr = curr.next\n",
    "            list1 = list1.next\n",
    "            \n",
    "        while list2:\n",
    "            curr.next = ListNode(list2.val)\n",
    "            curr = curr.next\n",
    "            list2 = list2.next\n",
    "\n",
    "        return head.next\n",
    "    \n",
    "    def merge(self, lists: List[ListNode], left: int, right: int):\n",
    "        if left == right:\n",
    "            return lists[left]\n",
    "        if left > right:\n",
    "            return None\n",
    "        mid = (left + right) // 2\n",
    "        \n",
    "        return self.mergeTow(self.merge(lists, left, mid), self.merge(lists, mid + 1, right))\n",
    "    \n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        return self.merge(lists, 0, len(lists) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def merge(self, l1: ListNode, l2: ListNode):\n",
    "        dummy = ListNode()\n",
    "        curr =dummy\n",
    "        while l1 and l2:\n",
    "            if l1.val > l2.val:\n",
    "                val = l2.val\n",
    "                l2 = l2.next\n",
    "            else:\n",
    "                val = l1.val\n",
    "                l1 = l1.next\n",
    "            curr.next = ListNode(val)\n",
    "            curr = curr.next\n",
    "        while l1:\n",
    "            curr.next = ListNode(l1.val)\n",
    "            l1 = l1.next\n",
    "            curr = curr.next\n",
    "        while l2:\n",
    "            curr.next = ListNode(l2.val)\n",
    "            l2 = l2.next\n",
    "            curr = curr.next\n",
    "        return dummy.next\n",
    "\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        if len(lists) == 1:\n",
    "            return lists[0]\n",
    "\n",
    "        q = Queue()\n",
    "        for r in lists:\n",
    "            q.put(r)\n",
    "\n",
    "        while q.qsize() != 1:\n",
    "            l1 = q.get()\n",
    "            l2 = q.get()\n",
    "            l3 = self.merge(l1, l2)\n",
    "            q.put(l3)\n",
    "\n",
    "        return q.get()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        def nodeiter(node):\n",
    "            while(node):\n",
    "                yield node \n",
    "                node = node.next \n",
    "        res = list(itertools.chain(*map(nodeiter,lists)))\n",
    "        if not res:\n",
    "            return None\n",
    "        res.sort(key = lambda x:x.val)\n",
    "        it = iter(res)\n",
    "        head = tail = next(it)\n",
    "        for node in it:\n",
    "            tail.next = tail = node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        def merge(node1,node2):\n",
    "            res=ListNode()\n",
    "            tmp=res\n",
    "            while node1 and node2:\n",
    "                if node1.val<=node2.val:\n",
    "                    tmp.next=ListNode(node1.val)\n",
    "                    tmp=tmp.next\n",
    "                    node1=node1.next\n",
    "                else:\n",
    "                    tmp.next=ListNode(node2.val)\n",
    "                    tmp=tmp.next\n",
    "                    node2=node2.next\n",
    "            while node1:\n",
    "                tmp.next=ListNode(node1.val)\n",
    "                tmp=tmp.next\n",
    "                node1=node1.next\n",
    "            while node2:\n",
    "                tmp.next=ListNode(node2.val)\n",
    "                tmp=tmp.next\n",
    "                node2=node2.next\n",
    "            return res.next\n",
    "        while len(lists)>1:\n",
    "            num=len(lists)//2\n",
    "            res=[]\n",
    "            for i in range(num):\n",
    "                res.append(merge(lists[i*2],lists[i*2+1]))\n",
    "            if len(lists)%2:\n",
    "                res.append(lists[-1])\n",
    "            lists=res\n",
    "        return lists[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, node):\n",
    "        self.node = node\n",
    "    def __lt__(self, other):\n",
    "        return self.node.val < other.node.val\n",
    "import copy\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if len(lists) == 0:\n",
    "            return None\n",
    "        my_q = PriorityQueue()\n",
    "        head = ListNode(0)\n",
    "        root = head\n",
    "        for i in range(len(lists)):\n",
    "            if lists[i] != None:\n",
    "                node = Node(lists[i])\n",
    "                my_q.put(node)\n",
    "        # print('111')\n",
    "        while my_q.qsize() != 0:\n",
    "            node_top = my_q.get()\n",
    "            node_o = node_top.node\n",
    "            root.next = copy.deepcopy(node_o)\n",
    "            if node_o.next != None:\n",
    "                my_q.put(Node(node_o.next))\n",
    "            root = root.next\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        def iterate(node):\n",
    "            while node:\n",
    "                yield node.val\n",
    "                node = node.next\n",
    "        dummy = cur = ListNode()\n",
    "        for x in heapq.merge(*map(iterate, lists)):\n",
    "            cur.next = cur = ListNode(x)\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        def it(node):\n",
    "            while node:\n",
    "                yield node.val\n",
    "                node = node.next\n",
    "        dummy = cur = ListNode()\n",
    "        for x in heapq.merge(*map(it, lists)):\n",
    "            cur.next = cur = ListNode(x)\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def __merge_list(self, l1, l2):\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        if l1.val < l2.val:\n",
    "            l1.next = self.__merge_list(l1.next, l2)\n",
    "            return l1\n",
    "        l2.next = self.__merge_list(l1, l2.next)\n",
    "        return l2\n",
    "\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        cur = None\n",
    "        for _list in lists:\n",
    "            if not cur:\n",
    "                cur = _list\n",
    "                continue\n",
    "            cur = self.__merge_list(cur, _list)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        # 方法1，两两疯狂融合\n",
    "        if len(lists) == 0:\n",
    "            return None\n",
    "        if len(lists) == 1:\n",
    "            return lists[0]\n",
    "        a = reduce(self.recurMerge,lists) # 这里采用了reduce语法\n",
    "        return a\n",
    "\n",
    "    def recurMerge(self,lst1,lst2): # 递归融合\n",
    "        if lst1 == None: return lst2\n",
    "        if lst2 == None: return lst1\n",
    "        if lst1.val < lst2.val:\n",
    "            lst1.next = self.recurMerge(lst1.next,lst2)\n",
    "            return lst1\n",
    "        else:\n",
    "            lst2.next = self.recurMerge(lst1,lst2.next)\n",
    "            return lst2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        if len(lists) == 1:\n",
    "            return lists[0]\n",
    "        res = lists[0]\n",
    "        for i in range(1, len(lists)):\n",
    "            head = lists[i]\n",
    "            res = self.merge(res, head)\n",
    "        return res\n",
    "\n",
    "    def merge(self, l, r):\n",
    "        if not l:\n",
    "            return r\n",
    "        if not r:\n",
    "            return l\n",
    "        if l.val < r.val:\n",
    "            l.next = self.merge(l.next, r)\n",
    "            return l\n",
    "        else:\n",
    "            r.next = self.merge(l, r.next)\n",
    "            return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        # # K 指针\n",
    "        # n, dummy_head = len(lists), ListNode()\n",
    "        # tail = dummy_head\n",
    "        # while True:\n",
    "        #     cur, point = None, -1\n",
    "        #     for i in range(n):\n",
    "        #         if not lists[i]:\n",
    "        #             continue\n",
    "        #         if not cur or cur.val > lists[i].val:\n",
    "        #             cur = lists[i]\n",
    "        #             point = i\n",
    "        #     if not cur:\n",
    "        #         break\n",
    "        #     tail.next = cur\n",
    "        #     tail = tail.next\n",
    "        #     lists[point] = lists[point].next\n",
    "        # return dummy_head.next\n",
    "\n",
    "        # 分治法\n",
    "        n, self.lists = len(lists), lists\n",
    "        return self.merge(0, n - 1)\n",
    "\n",
    "    def merge(self, left, right):\n",
    "        if left > right: return\n",
    "        if left == right: return self.lists[left]\n",
    "        mid = (left + right) // 2\n",
    "        l1 = self.merge(left, mid)\n",
    "        l2 = self.merge(mid + 1, right)\n",
    "        return self.merge_two_list(l1, l2)\n",
    "\n",
    "    def merge_two_list(self, l1, l2):\n",
    "        if not l1 or not l2:\n",
    "            return l1 or l2\n",
    "        if l1.val < l2.val:\n",
    "            l1.next = self.merge_two_list(l1.next, l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.merge_two_list(l1, l2.next)\n",
    "            return l2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        # # K 指针\n",
    "        # n, dummy_head = len(lists), ListNode()\n",
    "        # tail = dummy_head\n",
    "        # while True:\n",
    "        #     cur, point = None, -1\n",
    "        #     for i in range(n):\n",
    "        #         if not lists[i]:\n",
    "        #             continue\n",
    "        #         if not cur or cur.val > lists[i].val:\n",
    "        #             cur = lists[i]\n",
    "        #             point = i\n",
    "        #     if not cur:\n",
    "        #         break\n",
    "        #     tail.next = cur\n",
    "        #     tail = tail.next\n",
    "        #     lists[point] = lists[point].next\n",
    "        # return dummy_head.next\n",
    "\n",
    "        # 分治法\n",
    "        n, self.lists = len(lists), lists\n",
    "        return self.merge(0, n - 1)\n",
    "\n",
    "    def merge(self, left, right):\n",
    "        if left > right: return\n",
    "        if left == right: return self.lists[left]\n",
    "        mid = (left + right) // 2\n",
    "        l1 = self.merge(left, mid)\n",
    "        l2 = self.merge(mid + 1, right)\n",
    "        return self.merge_two_list(l1, l2)\n",
    "\n",
    "    def merge_two_list(self, l1, l2):\n",
    "        if not l1 or not l2:\n",
    "            return l1 or l2\n",
    "        if l1.val < l2.val:\n",
    "            l1.next = self.merge_two_list(l1.next, l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.merge_two_list(l1, l2.next)\n",
    "            return l2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if len(lists) == 0: return None\n",
    "        while len(lists) > 1:\n",
    "            new_list = []\n",
    "            for i in range(len(lists)//2):\n",
    "                new_list.append(self.mergeTwoLists(lists[2*i], lists[2*i+1]))\n",
    "            if len(lists) % 2:\n",
    "                new_list.append(lists[-1])\n",
    "            lists = new_list\n",
    "        return lists[0]\n",
    "\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        cur1, cur2 = l1, l2\n",
    "        if l1 is None: return l2\n",
    "        if l2 is None: return l1\n",
    "        if cur1.val > cur2.val:\n",
    "            head, base, attach = l2, l2, l1\n",
    "        else:\n",
    "            head, base, attach = l1, l1, l2\n",
    "        \n",
    "        while attach:\n",
    "            while base.next and base.next.val < attach.val:\n",
    "                base = base.next\n",
    "            if base.next is None:\n",
    "                base.next = attach; break\n",
    "            else:\n",
    "                tmp = ListNode(attach.val)\n",
    "                tmp.next = base.next\n",
    "                base.next = tmp\n",
    "            attach = attach.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if len(lists) == 0: return None\n",
    "        while len(lists) > 1:\n",
    "            new_list = []\n",
    "            for i in range(len(lists)//2):\n",
    "                lists[i] = self.mergeTwoLists(lists[2*i], lists[2*i+1])\n",
    "            if len(lists) % 2:\n",
    "                lists = lists[:len(lists)//2]+[lists[-1]]\n",
    "            else:\n",
    "                lists = lists[:len(lists)//2]\n",
    "        return lists[0]\n",
    "\n",
    "    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        cur1, cur2 = l1, l2\n",
    "        if l1 is None: return l2\n",
    "        if l2 is None: return l1\n",
    "        if cur1.val > cur2.val:\n",
    "            head, base, attach = l2, l2, l1\n",
    "        else:\n",
    "            head, base, attach = l1, l1, l2\n",
    "        \n",
    "        while attach:\n",
    "            while base.next and base.next.val < attach.val:\n",
    "                base = base.next\n",
    "            if base.next is None:\n",
    "                base.next = attach; break\n",
    "            else:\n",
    "                tmp = ListNode(attach.val)\n",
    "                tmp.next = base.next\n",
    "                base.next = tmp\n",
    "            attach = attach.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        minVal = float('inf')\n",
    "        minNode = None\n",
    "        minIdx = -1\n",
    "        for i, head in enumerate(lists):\n",
    "            if head:\n",
    "                if head.val < minVal:\n",
    "                    minVal = head.val\n",
    "                    minNode = head\n",
    "                    minIdx = i\n",
    "        if minNode is None:\n",
    "            return minNode\n",
    "        lists[minIdx] = lists[minIdx].next\n",
    "        last = self.mergeKLists(lists)\n",
    "        minNode.next = last\n",
    "        return minNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        def merge(l1,l2):\n",
    "            if not l1:\n",
    "                return l2\n",
    "            if not l2:\n",
    "                return l1\n",
    "            if l1.val<l2.val:\n",
    "                l1.next=merge(l1.next,l2)\n",
    "                return l1\n",
    "            else:\n",
    "                l2.next=merge(l1,l2.next)\n",
    "                return l2\n",
    "        n=len(lists)\n",
    "        if n==0:\n",
    "            return None\n",
    "        if n==1:\n",
    "            return lists[0]\n",
    "        while n!=1:\n",
    "            l1=lists.pop()\n",
    "            l2=lists.pop()\n",
    "            lists.append(merge(l1,l2))\n",
    "            n-=1\n",
    "        return lists[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        # 方法1：迭代，暴力解\n",
    "\n",
    "        res = None\n",
    "        for l in lists:\n",
    "            res = self.mergeTwoLists(res, l)\n",
    "        \n",
    "        return res\n",
    "\n",
    "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 方法2:迭代方法\n",
    "        if list1 is None:\n",
    "            return list2\n",
    "        elif list2 is None:\n",
    "            return list1\n",
    "        else:\n",
    "            if list1.val < list2.val:\n",
    "                res = list1\n",
    "                list1 = list1.next\n",
    "                res.next = self.mergeTwoLists(list1, list2)\n",
    "            else:\n",
    "                res = list2\n",
    "                list2 = list2.next\n",
    "                res.next = self.mergeTwoLists(list1, list2)\n",
    "             \n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:return\n",
    "        def merge_sort(start,end):\n",
    "            if start ==end:\n",
    "                return lists[start]\n",
    "            mid = (start + end)//2\n",
    "            left = merge_sort(start,mid)\n",
    "            right = merge_sort(mid +1, end)\n",
    "            return merge_list(left,right)\n",
    "            \n",
    "\n",
    "        def merge_list(left,right):\n",
    "            if not right:\n",
    "                return left\n",
    "            if not left:\n",
    "                return right\n",
    "            if left.val < right.val:\n",
    "                left.next = merge_list(left.next,right)\n",
    "                return left\n",
    "            else:\n",
    "                right.next = merge_list(left,right.next)\n",
    "                return right\n",
    "\n",
    "        return merge_sort(0,len(lists)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        def helper(i,j):\n",
    "            if i==j:\n",
    "                return lists[i]\n",
    "            mid=(i+j)//2\n",
    "            left=helper(i,mid)\n",
    "            right=helper(mid+1,j)\n",
    "            return merge(left,right)\n",
    "        def merge(a,b):\n",
    "            if not (a and b):\n",
    "                return a if a else b\n",
    "            if a.val<=b.val:\n",
    "                a.next=merge(a.next,b)\n",
    "                return a\n",
    "            else:\n",
    "                b.next=merge(a,b.next)\n",
    "                return b\n",
    "        return helper(0,len(lists)-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "\n",
    "        def merge(l1,l2):\n",
    "            if not l1:return l2\n",
    "            if not l2:return l1\n",
    "            if l1.val<=l2.val:\n",
    "                l1.next=merge(l1.next,l2)\n",
    "                return l1\n",
    "            else:\n",
    "                l2.next=merge(l1,l2.next)\n",
    "                return l2\n",
    "        res=None\n",
    "        for l in lists:\n",
    "            res=merge(res,l)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        def merge2Lists(l1: ListNode, l2: ListNode):\n",
    "            if l1 is None:\n",
    "                return l2\n",
    "            if l2 is None:\n",
    "                return l1\n",
    "            if l1.val < l2.val:\n",
    "                l1.next = merge2Lists(l1.next, l2)\n",
    "                return l1\n",
    "            else:\n",
    "                l2.next = merge2Lists(l1, l2.next)\n",
    "                return l2\n",
    "\n",
    "        if not lists:\n",
    "            return None\n",
    "        ans = None\n",
    "        for l in lists:\n",
    "            ans = merge2Lists(ans, l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        L = ListNode(-1)\n",
    "\n",
    "        def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:\n",
    "            if not l1: return l2  # 终止条件，直到两个链表都空\n",
    "            if not l2: return l1\n",
    "            if l1.val <= l2.val:  # 递归调用\n",
    "                l1.next = mergeTwoLists(l1.next, l2)\n",
    "                return l1\n",
    "            else:\n",
    "                l2.next = mergeTwoLists(l1, l2.next)\n",
    "                return l2\n",
    "\n",
    "        L.next = lists[0]\n",
    "        while len(lists) > 1:\n",
    "            L.next = mergeTwoLists(L.next, lists[-1])\n",
    "            lists.pop()\n",
    "        return L.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "\n",
    "        if len(lists)==0:\n",
    "            return None\n",
    "        if len(lists) == 1:\n",
    "            return lists[0]\n",
    "        if len(lists) == 2:\n",
    "            return self.merge2Lists(lists[0], lists[1])\n",
    "\n",
    "        length = len(lists)\n",
    "        half = length //2\n",
    "\n",
    "        p1 = self.mergeKLists(lists[:half])\n",
    "        p2 = self.mergeKLists(lists[half:])\n",
    "\n",
    "        return self.merge2Lists(p1,p2)\n",
    "\n",
    "\n",
    "    def merge2Lists(self, list1, list2):\n",
    "        if not list1:\n",
    "            return list2\n",
    "        if not list2:\n",
    "            return list1\n",
    "        \n",
    "        if list1.val > list2.val: # list2 放到前面 升序排队\n",
    "            tmp = self.merge2Lists(list1, list2.next)\n",
    "            list2.next = tmp\n",
    "            return list2 \n",
    "\n",
    "        else: #list1 放到前面 升序\n",
    "            tmp = self.merge2Lists(list1.next, list2)\n",
    "            list1.next =tmp\n",
    "            return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
    "        if not lists:\n",
    "            return \n",
    "        n = len(lists)\n",
    "        return self.merge(lists, 0, n-1)\n",
    "    \n",
    "    def merge(self, lists, left , right):\n",
    "        if left==right:\n",
    "            return lists[right]\n",
    "        mid = (left+right)//2\n",
    "        l1 = self.merge(lists, left, mid)\n",
    "        l2 = self.merge(lists, mid+1, right)\n",
    "        return self.mergeTwoLinknode(l1, l2)\n",
    "    \n",
    "    def mergeTwoLinknode(self, l1, l2):\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        if l1.val<l2.val:\n",
    "            l1.next = self.mergeTwoLinknode(l1.next, l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.mergeTwoLinknode(l1, l2.next)\n",
    "            return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        if len(lists) == 1:\n",
    "            return lists[0]\n",
    "        mid = len(lists) // 2\n",
    "        left = self.mergeKLists(lists[:mid])\n",
    "        right = self.mergeKLists(lists[mid:])\n",
    "        return self.merge(left, right)\n",
    "\n",
    "    def merge(self, l1, l2):\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        if l1.val < l2.val:\n",
    "            l1.next = self.merge(l1.next, l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.merge(l1, l2.next)\n",
    "            return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if len(lists)==0:\n",
    "            return None\n",
    "        \n",
    "        idx = -1\n",
    "        minNum = 10**5\n",
    "        for i in range(len(lists)):\n",
    "            if lists[i]!=None and lists[i].val<minNum:\n",
    "                idx = i\n",
    "                minNum = lists[i].val\n",
    "        if idx == -1:\n",
    "            return None\n",
    "\n",
    "        curNode = lists[idx]\n",
    "        lists[idx] = lists[idx].next\n",
    "        curNode.next = self.mergeKLists(lists)\n",
    "        return curNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        min_val = float('inf')\n",
    "        min_idx = float('inf')\n",
    "        for i, node in enumerate(lists):\n",
    "            if node and node.val<min_val:\n",
    "                min_val = node.val\n",
    "                min_idx = i\n",
    "        if min_val==float('inf'):\n",
    "            return None\n",
    "        head = lists[min_idx]\n",
    "        lists[min_idx] = lists[min_idx].next\n",
    "        head.next = self.mergeKLists(lists)\n",
    "\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def merge_2_list(self, list1, list2):\n",
    "        if not list1:\n",
    "            return list2\n",
    "        if not list2:\n",
    "            return list1\n",
    "        if list1.val < list2.val:\n",
    "            list1.next = self.merge_2_list(list1.next, list2)\n",
    "            return list1\n",
    "        else:\n",
    "            list2.next = self.merge_2_list(list1, list2.next)\n",
    "            return list2\n",
    "\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        r = None\n",
    "        for lst in lists:\n",
    "            r = self.merge_2_list(r, lst)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        ans = None\n",
    "        for list in lists:\n",
    "            ans = self.merge(ans,list)\n",
    "        return ans\n",
    "    def merge(self, list1,list2):\n",
    "        if not list1:\n",
    "            return list2\n",
    "        elif not list2:\n",
    "            return list1\n",
    "        else:\n",
    "            if list1.val <= list2.val:\n",
    "                list1.next = self.merge(list1.next,list2)\n",
    "                return list1\n",
    "            else:\n",
    "                list2.next = self.merge(list2.next,list1)\n",
    "                return list2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        if not lists:\n",
    "            return None\n",
    "        # 合并链表\n",
    "        def merge(node1, node2):\n",
    "            if not (node1 and node2):\n",
    "                return node1 if node1 else node2\n",
    "            if node1.val <= node2.val:\n",
    "                node1.next = merge(node1.next, node2)\n",
    "                return node1\n",
    "            else:\n",
    "                node2.next = merge(node1, node2.next)\n",
    "                return node2\n",
    "        res = lists[0]\n",
    "        for i in range(1, len(lists)):\n",
    "            res = merge(res, lists[i])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        def merge(l1, l2):\n",
    "            if not l1:\n",
    "                return l2\n",
    "            if not l2:\n",
    "                return l1\n",
    "            if l1.val <= l2.val:\n",
    "                l1.next = merge(l1.next, l2)\n",
    "                return l1\n",
    "            else:\n",
    "                l2.next = merge(l1, l2.next)\n",
    "                return l2\n",
    "        l = len(lists)\n",
    "        if not l:\n",
    "            return\n",
    "        if l == 1:\n",
    "            return lists[0]\n",
    "        mid = l // 2\n",
    "        l1 = self.mergeKLists(lists[:mid])\n",
    "        l2 = self.mergeKLists(lists[mid:])\n",
    "        res = merge(l1, l2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeKLists(self, lists: List[ListNode]) -> ListNode:\n",
    "        def merge(a, b):\n",
    "            if not a:\n",
    "                return b\n",
    "            if not b:\n",
    "                return a\n",
    "            if a.val <= b.val:\n",
    "                a.next = merge(a.next, b)\n",
    "                return a\n",
    "            else:\n",
    "                b.next = merge(a, b.next)\n",
    "                return b\n",
    "        n = len(lists)\n",
    "        if not n:\n",
    "            return\n",
    "        if n == 1:\n",
    "            return lists[0]\n",
    "        mid = n // 2\n",
    "        a = self.mergeKLists(lists[:mid])\n",
    "        b = self.mergeKLists(lists[mid:])\n",
    "        res = merge(a, b)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
